sliding Window 是 Two Pointer 技巧的一部分，通常用於解決連續子陣列（或子字串）的問題。

Sliding Window 模板

這模板是翻到我自己的筆記，其資料來源(應該)是來自 刷題實戰筆記：演算法工程師求職加分的祕笈這本書
sliding window 的模板:

right_ptr = 0, left_ptr = 0 ，代表左閉右開的視窗區間

1. 先將rptr 擴大可行解區域
2. 接著換 lptr 移動，縮小可行解，將達到解的最佳化!

做 sliding window 題目需要回答:

1. rptr 擴大時，要新增甚麼資料?
2. 何時移動 lptr ?
3. lptr 縮小可行解時，要移除甚麼資料?
4. 結果是該在 rptr 還是 lptr 移動時做更新?

loop invariant (迴圈不變性)

Python-LeetCode 581 第二招 Sliding Window，吳邦一教授提及重要概念 「迴圈不變性」:

複雜的問題與程式當然需要分成很多步驟，但對於一個區段或一個小副程式，答案往往就在迴圈不變性，背後的道理其實也就是數學歸納法。

不變性 簡單說，若第 i 步對，那麼第 i+1 步也是對的
因此無論滑動視窗在擴大或縮小，要維護的某性質都沒有被改動到，視窗仍是可行解區域!

3. Longest Substring Without Repeating Characters (medium)

題目描述: 給字串 s，找到不包含重複字元的最長子字串

使用 [刷題實戰筆記] 的 sliding windows 中問題 來解題:
使用 [lptr, rptr) 代表視窗區間。

Q: 當擴大 rptr 時加入甚麼值? A: 加入陣列的第 rptr 的值
Q: 何時要移動 lptr? 當 rptr 重複。
因此需要有個 map 紀錄 windows 內是否有字元重複。

這題的迴圈不變性為 lptr 起的視窗內沒有重複的字元

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left = 0, right = 0;
        int ans = 0;
        unordered_map<char, int> count;
        
        while(right < s.size()){
            // rptr moves
            count[s[right++]] ++;
            
            //lptr moves
            while(count[s[right-1]] > 1){               
                count[s[left++]] --;
            }

            ans = max(ans, right-left);
        }
        return ans;
    }
};

(這題可以像吳邦一教授一樣 開 255 長度的陣列 取代 map 的使用)

時間複雜度: rptr 與 lptr 沒有回頭，故 O(n)

1456. Maximum Number of Vowels in a Substring of Given Length (medium)

題目敘述: 給字串 s 與 正數 k，返回有最多母音數在長度為 k 的 substring 。

教授說到這題的

迴圈不變性是 cnt 是視窗內母音的個數。 (我的程式裡是ctr)

解題思路:
將長度 k 的子字串視為一個視窗，接著逐步滑動視窗到遍歷整個 s。

在以下程式， maxVowels 函式裡的第一個 for loop ，目的是要得到 ctr 的值 。接著第二個 for loop 就是逐一將視窗向右移一位，過程中要更新 ctr。

class Solution {
public:
    bool isVowel (char s) {
        if (s == 'a' || s == 'e' || s == 'i' || s == 'o' || s == 'u')
            return true;
        return false;
    }
    int maxVowels(string s, int k) {
        int ctr = 0, res = 0;
        for (int rptr = 0; rptr < k; rptr++) {
            if (isVowel(s[rptr])) ctr++;
        }
        res = ctr;
        for (int rptr = k; rptr < s.size(); rptr++) {
            if (isVowel(s[rptr-k])) ctr -= 1;
            if (isVowel(s[rptr])) ctr += 1;
            res = max(ctr, res); 
        }
        return res;
    }
};

643. Maximum Average Subarray I (easy) 的解題思路與這題一模一樣，在固定長度的視窗滑動時做增刪值。

明天續寫 sliding window 的相關題目 1004. Max Consecutive Ones III (medium)、30. Substring with Concatenation of All Words